package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 63. 股票的最大利润 https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/
 * 题目简述：给定一个数组prices ，它的第i个元素prices[i]表示股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。计算所能获取的最大利润。
 */
public class MaxProfit {

    /**
     * 思路一：从左向右扫描，记录已扫描区间最小值low，并计算当前价格与其差值然后更新利润，最后更新low，再继续向后扫描。
     */
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int low = prices[0], result = 0;
        for (int i = 1;i < prices.length;i++) {
            //计算与前面的最小值low的差值用于更新利润
            result = Math.max(result, prices[i] - low);
            //更新已扫描区间最小值lo
            low = Math.min(low, prices[i]);
        }
        return result;
    }

    /**
     * 动态规划
     * 1. 定义dp: dp[i][0]为第i天不持有股票时的最大现金，dp[i][1]为第i天持有股票时的最大现金
     * 2. 状态转移公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     *               dp[i][1] = max(dp[i-1][1], -prices[i])
     * 3. 初始化：dp[0][0] = 0, dp[0][1] = -prices[0]
     * 4. 开始遍历
     */
    public int maxProfit2(int[] prices) {
        if (prices.length < 2) return 0;
        int dpi0 = 0, dpi1 = -prices[0], profit = 0;
        for (int i = 1;i < prices.length;i++) {
            dpi0 = Math.max(dpi0, dpi1 + prices[i]);
            dpi1 = Math.max(dpi1, -prices[i]);
            profit = Math.max(profit, dpi0);
        }
        return profit;
    }
}
